class Node:
    prev: 'Node'
    next: 'Node'

    def __init__(self, val=None, key=None):
        self.val = val
        self.key = key


class LRUCache:

    def __init__(self, capacity: int):
        self.h = dict()
        self.mx = capacity
        head = Node()
        tail = Node()
        head.next = tail
        head.prev = None
        tail.next = None
        tail.prev = head
        self.head = head
        self.tail = tail

    def insert(self, node: Node):
        first = self.head.next
        self.head.next = node
        first.prev = node
        node.prev = self.head
        node.next = first

    def move(self, node: Node):
        prev = node.prev
        next = node.next
        prev.next = next
        next.prev = prev
        first = self.head.next
        self.head.next = node
        first.prev = node
        node.prev = self.head
        node.next = first

    def delete(self):
        node = self.tail.prev
        self.h.pop(node.key)
        prev = node.prev
        prev.next = self.tail
        self.tail.prev = prev

    def get(self, key: int) -> int:
        if key in self.h:
            node = self.h.get(key)
            self.move(node)  # 这个节点移动到头部
            return node.val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.h:
            node = self.h.get(key)
            node.val = value
            self.move(node)  # 这个节点移动到头部
            return
        # 上限判定
        if len(self.h) == self.mx:
            self.delete()  # 删除旧未用的
        # 插入数据
        node = Node(val=value, key=key)
        self.h[key] = node
        self.insert(node)  # 这个节点插入到头部


lRUCache = LRUCache(2)
lRUCache.put(1, 1)
# 缓存是 {1=1}
lRUCache.put(2, 2)
# 缓存是 {1=1, 2=2}
lRUCache.get(1)
# 返回 1
lRUCache.put(3, 3)
# 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2)
# 返回 -1 (未找到)
lRUCache.put(4, 4)
# 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1)
# 返回 -1 (未找到)
lRUCache.get(3)
# 返回 3
lRUCache.get(4)
# 返回 4
